﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <algorithm>
#include <ios>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

class LRUCache {
public:
    struct Node {
        Node* next;
        Node* pre;
        int key;
        int value;
        Node() :next(nullptr), pre(nullptr), key(0), value(0) {}
        Node(int key, int value) :next(nullptr), pre(nullptr), key(key), value(value) {}
    };

    void addtoHead(Node* node)
    {
        head->next->pre = node;
        node->next = head->next;
        head->next = node;
        node->pre = head;
    }

    void removeNode(Node* node)
    {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }

    void movetohead(Node* node)
    {
        removeNode(node);
        addtoHead(node);
    }

    Node* removeTail()
    {
        Node* node = tail->pre;
        removeNode(node);
        return node;
    }

    LRUCache(int capacity)
        :_capacity(capacity), size(0)
    {
        head = new Node();
        tail = new Node();
        head->next = tail;
        head->pre = tail;
        tail->pre = head;
        tail->next = head;
    }

    int get(int key) {
        if (!mp.count(key)) return -1;

        Node* node = mp[key];
        movetohead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (mp.count(key))
        {
            Node* node = mp[key];
            node->value = value;
            movetohead(node);
        }
        else
        {
            Node* node = new Node(key, value);
            addtoHead(node);
            mp[key] = node;
            size++;
            if (size > _capacity)
            {
                Node* tmp = removeTail();
                mp.erase(tmp->key);
                delete tmp;
                size--;
            }
        }
    }

private:
    Node* head;
    Node* tail;
    int _capacity;
    int size;
    unordered_map<int, Node*> mp;
};


int main() {
   
}
// 64 位输出请用 printf("%lld")
//1 1 1
//1 0 0
//1 0 0
//1 0 0